/*******************************************************************************
 * Witz - Winboard Chess Engine                                                *
 * BITINSTRUCTIONS.C                                                           *
 *                                                                             *
 * Contrains routines such as population count and logrithm.                   *
 *                                                                             *
 * Please refer to the licence notice in MAIN.C                                *
 *                                                                             *
 * Copywright (C) 2006 Pradu Kannan                                            *
 * http://witz.sf.net/                                                         *
 ******************************************************************************/

#include "build.h"
#include "defs.h"
#include "data.h"

/*popCount()
 *a table lookup version of population Count
 *this happens to be 2x faster than Heinz's method in Dark Thought
 *
 *@param b - the quadword to be counted
 *@returns the number of 1 bits in b
 */
int popCount(const U64 b)
{
    return population[b&0xFFFF]+population[(b>>16)&0xFFFF]+population[(b>>32)&0xFFFF]+population[(b>>48)&0xFFFF];
}

/*iterativePopCount()
 *an iterative population count of 1 bits in a quadword
 *this population count is better than the regular population count if the
 *number of 1 bits is sparce (usually less than 5 bits)
 *
 *@param b - the quadword to be counted
 *@returns the number of 1 bits in b
 */
int iterativePopCount(U64 b)
{
    int n;
    for (n = 0; b != 0; n++, b &= (b - 1));
    return n;
}

/*Log2()
 *finds the reverse LogBase2 of a 64 bit number that is a power of 2
 *it also has the side effect of finding the most significant 1 bit
 *My Log2 algorithm works faster  than the de Bruijn bitscan.
 *
 *@param x - a 64 bit number
 *@returns - the reverse LogBase2
 */
int Log2(const U64 x)
{
	U32 temp,temp2;
	if(temp=(U32)(x>>32))
	{
		if(temp2=(U32)(temp>>16))
			return 48+LogTable[temp2];
		return 32+LogTable[temp];
    }
	if(temp=(U32)(x>>16))
	     return 16+LogTable[temp];
	return LogTable[x];
}

/*fillUp()
 *fills all bits above all 1 bits in a bitboard
 *
 *@param b - a bitboard
 *
 *@returns a bitboard with all bits above b filled up (discluding b)
 */
U64 fillUp(U64 b)
{
	b|=b<<8;
	b|=b<<16;
	return (b|(b<<32))<<8;
}

/*fillDown()
 *fills all bits below all 1 bits in a bitboard
 *
 *@param b - a bitboard
 *
 *@returns a bitboard with all bits below b filled down (discluding b)
 */
U64 fillDown(U64 b)
{
	b|=b>>8;
	b|=b>>16;
	return (b|(b>>32))>>8;
}

/*fillUp2()
 *fills all bits above all 1 bits in a bitboard
 *
 *@param b - a bitboard
 *
 *@returns a bitboard with all bits above b filled up (including b)
 */
U64 fillUp2(U64 b)
{
	b|=b<<8;
	b|=b<<16;
	return b|(b<<32);
}

/*fillDown2()
 *fills all bits below all 1 bits in a bitboard
 *
 *@param b - a bitboard
 *
 *@returns a bitboard with all bits below b filled down (including b)
 */
U64 fillDown2(U64 b)
{
	b|=b>>8;
	b|=b>>16;
	return b|(b>>32);
}

/*
U64 fillUpOccluded(U64 g, U64 p)
{
g |= p & (g << 8);
p &= (p << 8);
g |= p & (g << 16);
p &= (p << 16);
return g |= p & (g << 32);
}

U64 fillDownOccluded(U64 g, U64 p)
{
g |= p & (g >> 8);
p &= (p >> 8);
g |= p & (g >> 16);
p &= (p >> 16);
return g |= p & (g >> 32);
}
*/